package offer_2._63_maxProfit;

import java.util.ArrayList;

class Solution {
    // 暴力写法
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (max < prices[j] - prices[i])
                    max = prices[j] - prices[i];
            }
        }
        return max;
    }

    // 动态规划dp
    public int maxProfit1(int[] prices) {
        if (prices.length == 0)
            return 0;
        int n = prices.length;
        int[] dp = new int[n];

        int minValue = prices[0];
        for (int i = 1; i < n; i++) {
            minValue = Math.min(minValue, prices[i]);
            dp[i] = Math.max(dp[i - 1], prices[i] - minValue);
        }
        return dp[n - 1];

    }

    public int maxProfit2(int[] prices) {
        int minValue = Integer.MAX_VALUE;
        int maxValue = 0;
        for (int p : prices) {
            minValue = Math.min(p, minValue);
            maxValue = Math.max(maxValue, p - minValue);
        }
        return maxValue;
    }
}